package bfs;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

//本题思路和最小基于变化一模一样，甚至代码都几乎一模一样；
public class 单词接龙 {
	public static int l,r;
    public static String[] queue=new String[5001];
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> visit=new HashSet<>(); //记录已经访问过的元素
        Set<String> dict=new HashSet<>();  //字典库
        for(String s:wordList) dict.add(s);

        //如果结果不在字典库||开始字符串=结尾字符串，直接返回0
        if(!dict.contains(endWord)||beginWord.equals(endWord)) return 0;

        l=r=0;
        queue[r++]=beginWord;
        visit.add(beginWord);
        //用于枚举每个位置的可能值
        char[] array=new char[26];
        for(int i=0;i<26;i++){
            array[i]=(char)('a'+i);
        }
        int step=0;
        while(l<r){
            step++;
            int size=r-l;
            //按层处理，枚举每层的每个字符串
            for(int k=0;k<size;k++){
                String s=queue[l++];
                //枚举字符串的每个位置
                for(int i=0;i<s.length();i++){
                    char[] tmp=s.toCharArray();
                    //枚举每个位置的可能值
                    for(int j=0;j<26;j++){
                        tmp[i]=array[j];
                        String str=new String(tmp);
                        //如果未访问过并且字典中存在，则加入队列
                        if(dict.contains(str)==true&&visit.contains(str)==false){
                            if(str.equals(endWord)) return step+1;
                            queue[r++]=str;
                            visit.add(str);
                        }
                    }
                }
            }
        } 
        return 0;
    }
}
